
// leetcode 322. 零钱兑换
//class Solution {
//    public int coinChange(int[] coins, int amount) {
//        // 这道题可以用动态规划，就是背包问题
//        // 硬币就是物品，amount 就是背包
//        // 则 dp[j] 表示装满 j 背包所需要的最小硬币个数
//        // dp[j] = min(dp[j], dp[j - coins[i]] + 1)
//        int[] dp = new int[amount + 1];
//        Arrays.fill(dp, 1000000);
//        dp[0] = 0;
//        for (int i = 0; i < coins.length; i++) {
//            for (int j = coins[i]; j <= amount; j++) {
//                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
//            }
//        }
//        return dp[amount] == 1000000 ? -1 : dp[amount];
//    }
//}


// leetcode 139. 单词拆分
//class Solution {
//    public boolean wordBreak(String s, List<String> wordDict) {
//        // 还是背包问题，求单词是否能装满字符串，对单词的顺序有要求
//        // dp[i] 是否能装满长度为 i 字符串，与单词顺序有关，所以是排列，需要先遍历背包
//        // dp[i] 则看 dp[i - j] &&  [i,j] 的字符串在 word 数组内
//        // dp[i] = true;
//        boolean[] dp = new boolean[s.length() + 1];
//        dp[0] = true;
//        Set<String> set = new HashSet<>();
//        for (String str : wordDict) {
//            set.add(str);
//        }
//        for (int i = 1; i <= s.length(); i++) {
//            // j < i 是为了防止数组越界，要截取 j-i 长度的字符串
//            for (int j = 0; j < i; j++) {
//                String tmp = s.substring(j, i);
//                if (dp[j] && set.contains(tmp)) {
//                    dp[i] = true;
//                }
//            }
//        }
//        return dp[s.length()];
//    }
//}


// leetcode 300. 最长递增子序列
//class Solution {
//    public int lengthOfLIS(int[] nums) {
//        // 动态规划
//        // dp[i] 表示下标为 i 的最长递增子序列的长度
//        // dp[i] j=(0, i) && nums[i] > nums[j] ,max dp[j] + 1
//        int[] dp = new int[nums.length];
//        Arrays.fill(dp, 1);
//        for (int i = 1; i < dp.length; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[i] > nums[j]) {
//                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//                }
//            }
//        }
//        int max = 1;
//        for (int i = 0; i < dp.length; i++) {
//            max = Math.max(max, dp[i]);
//        }
//        return max;
//    }
//}


// leetcode 152. 乘积最大子数组
//class Solution {
//    public int maxProduct(int[] nums) {
//        // 动态规划
//        // dp[i] 表示以 i 下标为结尾的最大子数组乘积
//        // dp[i] = max(nums[i], dp[i - 1] * nums[i])
//        // 这样，考虑到数组可能存在多个负数
//        // 就可以将数组的最大值跟最小值都记录下来
//        // 之后 dp[i] 就比较最大值和最小值以及本身来决定
//        // 可以用一个二维数组来记录最小值和最大值
//        // dp[i][0] 表示最小值, dp[i][1] 表示最大值
//        int[][] dp = new int[nums.length][2];
//        // 初始化
//        for (int i = 0; i < dp.length; i++) {
//            dp[i][0] = nums[i];
//            dp[i][1] = nums[i];
//
//        }
//        for (int i = 1; i < dp.length; i++) {
//            int max = Math.max(nums[i], Math.max(dp[i - 1][1] * nums[i], dp[i - 1][0] * nums[i]));
//            int min = Math.min(nums[i], Math.min(dp[i - 1][1] * nums[i], dp[i - 1][0] * nums[i]));
//            dp[i][0] = min;
//            dp[i][1] = max;
//
//        }
//        int max = dp[0][1];
//        for (int i = 0; i < dp.length; i++) {
//            max = Math.max(max, dp[i][1]);
//        }
//        return max;
//    }
//}


// leetcode 416. 分割等和子集
//class Solution {
//    public boolean canPartition(int[] nums) {
//        // 动态规划，还是背包问题
//        // dp[j] 表示是否能装满 j 的背包
//        // dp[j] = dp[j] || dp[j - nums[i]]
//        double sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        sum /= 2;
//        int target = (int) sum;
//        // 如果 target 和 sum 不相等，则说明不能分成两份子数组
//        if (target != sum) return false;
//
//        boolean[] dp = new boolean[target + 1];
//        dp[0] = true;
//
//        // 先物品再背包，背包逆序也是因为物品 只能使用一次
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = target; j >= nums[i]; j--) {
//                dp[j] |= dp[j - nums[i]];
//            }
//        }
//        return dp[target];
//    }
//}

// leetcode 32. 最长有效括号
//class Solution {
//    public int longestValidParentheses(String s) {
//        if (s == null || s.length() == 0) return 0;
//        Stack<Integer> stack = new Stack<>();
//        stack.push(-1);// 防止越界
//        int maxCount = 0;
//        // 栈底元素(最后元素)始终维护最后一个没有匹配的右括号下标
//        // 遇到左括号就入栈，如果遇到右括号，就直接出栈，
//        // 此时若栈为空，就将当前右括号下标加入栈中(遵守规则),
//        // 若不为空，则更新结果
//        for (int i = 0; i < s.length(); i++) {
//            char ch = s.charAt(i);
//            if (ch == '(') {
//                stack.push(i);
//            } else {
//                stack.pop();
//                if (stack.isEmpty()) {
//                    stack.push(i);
//                } else {
//                    // 栈不为空
//                    maxCount = Math.max(maxCount, i - stack.peek());
//                }
//            }
//        }
//        return maxCount;
//    }
//}